package top;

/**
 * @author chenyw
 * @date 2022/7/7 21:31
 * @description     快速幂,分治法，
 *      方法1. 睁着推不好推，不知道最后要成几个x，所以反着推，如果是奇数就剁成一个x
 *      方法2. 将指数变成二进制
 */
public class Top50myPow {
//    public double myPow(double x, int n) {
//        double res = 1.0;
//        for (int i = n;i != 0;i /= 2) {
//            if ((i % 2) != 0) {
//                res *= x;
//            }
//            x *= x;
//        }
//        return (n >= 0)?res:1 / res;
//    }

    public double myPow(double x, int n) {
        if (x == 0.0f) {
            return 0.0d;
        }
        long i = n;
        i = Math.abs(i);
        double res = 1.0;
        while (i > 0) {
            if ((i & 1) == 1) {
                res *= x;
            }
            i >>= 1;
            x *= x;
        }
        return n>0?res:1/res;
    }
}
